Section: New Results

Arithmetic and Algorithms

Participants : Guillaume Hanrot, Claude-Pierre Jeannerod, Adeline Langlois, Ivan Morel, Christophe Mouilleron, Andrew Novocin, Xavier Pujol, Damien Stehlé, Gilles Villard.

Faster Lattice Reduction

Andrew Novocin, Damien Stehlé and Gilles Villard [40] designed an algorithm, ${\tilde{L}}^1$, with the following specifications: It takes as input an arbitrary basis $B$ in $Z^{d\times d}$ of a lattice $L$; It computes a basis of $L$ which is reduced for a mild modification of the Lenstra-Lenstra-Lovász reduction; It terminates in time $\tilde{O}(d^5\beta +d^{\omega +1}\beta )$ where $\beta =log\parallel B\parallel$ (and $\omega$ is a valid exponent for matrix multiplication). This is the first LLL-reducing algorithm with a time complexity that is quasi-linear in the bit-length beta of the entries and polynomial in the dimension $d$. A critical ingredient for achieving this result was the study of the effect of small perturbations on the LLL-reducedness of a lattice basis [17] .

Computing Short Lattice Vectors

Among all known lattice reduction algorithms, BKZ provides the best trade-off between run-time and smallness of the computed lattice basis. Guillaume Hanrot, Xavier Pujol and Damien Stehlé [32] showed that BKZ can be terminated long before its completion, while still providing bases of excellent quality. More precisely, if it is terminated within a polynomial number of calls to a lower-dimensial Shortest Vector Problem solver, then the bounds on the output quality are as close as desired to the bounds that can be obtained by letting BKZ run until completion.

Guillaume Hanrot, Xavier Pujol and Damien Stehlé also surveyed the known algorithms for solving the Shortest Vector Problem [31] .

Lattice-Based Cryptography

NTRUEncrypt is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers could make it a desirable alternative to factorisation and discrete-log based encryption schemes. Damien Stehlé and Ron Steinfeld [41] showed how to modify NTRUEncrypt to make it provably resistance to Chosen Plaintext Attacks, under the assumed quantum hardness of standard worst-case lattice problems restricted to a family of lattices related to some cyclotomic fields.

Lattices and Communication Theory

Cong Ling, Shuiyin Liu, Laura Luzzi and Damien Stehlé studied and optimized lattice algorithms that are relevant for MIMO communications [23] , [37] . These algorithms tackle the Bounded Distance Decoding Problem: Given a point within a small prescribed distance to a given lattice, find the lattice vector closest to it.

Other Applications of Lattice Reduction Algorithms

In [35] Jürgen Klüners, Mark van Hoeij, and Andrew Novocin showed how to use the LLL lattice reduction algorithm for computing a compact representation of the set of all subfields of any given number field. William Hart (Warwick Mathematics Institute, UK), Mark van Hoeij (Florida State University, USA) and Andrew Novocin exploited the very latest progress in lattice reduction to propose a fine-tuned cutting-edge implementation of a polynomial factorization algorithm.

Polynomial Arithmetic

With William Hart and Mark van Hoeij, A. Novocin proposed in [33] a state of the art algorithm for factoring polynomials in Z[x] . The algorithm is fast in practice, saving in a large class of common examples, without sacrificing performance on worst-case polynomials. The presented algorithm is structured along the lines of algorithms with the best theoretical complexity. In [34] William Hart and A. Novocin proposed an efficient algorithm for computing the composition of two univariate polynomials. Their work builds upon the Brent-Kung algorithm.

Exact Linear Algebra

Transforming a matrix over a field to echelon form, or decomposing the matrix as a product of structured matrices that reveal the rank profile, is a fundamental building block of computational exact linear algebra. For such tasks the best algorithms available so far were either rank sensitive (i.e., of complexity expressed in terms of the exponent of matrix multiplication and the rank of the input matrix) or in place (i.e., using essentially no more memory that what is needed for matrix multiplication). In [61] C.-P. Jeannerod, Clément Pernet (U. Joseph Fourier, Grenoble), and Arne Storjohann (U. Waterloo, Canada) have proposed algorithms that are both rank sensitive and in place. These algorithms are based on a new matrix factorization, namely $A=CUP$ with $C$ a column echelon form revealing the row rank profile of $A$, $U$ a unit upper triangular matrix, and $P$ a permutation matrix.